package com.azure.code.slidingwindow;

import java.util.HashMap;
import java.util.Map;

/**
 * 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
 * 。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 */
public class MinWindow_76 {

    public String minWindow(String s,String t) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0,right = 0;
        int valid = 0;
        // 记录最小覆盖子串的起始窗口
        int start = 0,len = Integer.MAX_VALUE;
        char[] arr = s.toCharArray();
        while (right<s.length()){
            // c是将移入到窗口的字符
            char c = s.charAt(right);
            // 扩大窗口
            right++;
            // 对窗口进行一些列的收缩
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(need.get(c).equals(window.get(c))){
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (valid==need.size()){
                // 这里更新最小覆盖子串
                if(right-left < len) {
                    start = left;
                    len = right-left;
                }
                char d = s.charAt(left);
                left++;
                // 进行窗口更新
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }

        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }

    public static void main(String[] args) {
        System.out.println(new MinWindow_76().minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(new MinWindow_76().minWindow("a", "a"));
        System.out.println(new MinWindow_76().minWindow("a", "aa"));
    }

}
